package com.flute.framework.autoprompt;

import java.util.Comparator;
import java.util.List;

public class BinaryInsertion<T> {

	public void insertMaxToMin(List<T> list, T d, Comparator<T> comparator) {

		int start = 0;
		int end = list.size() - 1;
		if (list.size() == 0) {
			list.add(d);
		} else if (comparator.compare(d, list.get(start)) >= 0) {
			list.add(start, d);
		} else if (comparator.compare(list.get(end), d) >= 0) {
			list.add(d);
		} else {
			while (true) {
				if (end <= start) {
					list.add(start, d);
					break;
				} else {
					int middle = (start + end) / 2;
					if (comparator.compare(list.get(middle), d) >= 0) {
						if (start == middle) {
							list.add(end, d);
							break;
						} else {
							start = middle;
						}
					} else if (comparator.compare(d, list.get(middle)) >= 0) {
						if (end == middle) {
							list.add(start, d);
							break;
						} else {
							end = middle;
						}
					}
				}
			}
		}
	}

	public T findMaxToMin(List<T> list, T t, Comparator<T> comparator) {
		int start = 0;
		int end = list.size() - 1;

		if (list.size() == 0) {
			return null;
		}
		if (comparator.compare(t, list.get(start)) > 0) {
			return null;
		} else if (comparator.compare(t, list.get(end)) < 0) {
			return null;
		} else if (comparator.compare(t, list.get(start)) == 0) {
			return list.get(start);
		} else if (comparator.compare(t, list.get(end)) == 0) {
			return list.get(end);
		} else {
			while (start < end) {
				int middle = (start + end) / 2;
				if (comparator.compare(t, list.get(middle)) == 0) {
					return list.get(middle);
				} else if (comparator.compare(t, list.get(middle)) > 0) {
					if (end == middle) {
						return null;
					} else {
						end = middle;
					}
				} else if (comparator.compare(t, list.get(middle)) < 0) {
					if (start == middle) {
						return null;
					} else {
						start = middle;
					}
				}
			}
		}

		return null;
	}
}
